#include <iostream>
using namespace std;

template<typename T>
class List {
  struct Node {
    Node* next;
    T data;
    Node(const T& t) : next(), data(t) {}
  };
  Node* m_tail; // 尾节点指针。列表如果非空，尾节点的next指向头节点。
public:
  List() : m_tail() {}
  List(const List<T>& lst) = delete;
  List(List<T>&& lst) = delete;
  List& operator=(const List<T>& lst) = delete;
  List& operator=(List<T>&& lst) = delete;

  ~List() {
    if(!m_tail) {
      return;
    }
    for(auto pt = m_tail->next;;) {
      auto pn = pt->next;
      delete pt;
      if(pt == m_tail) {
        break;
      } else {
        pt = pn;
      }
    }
  }

  void swap(List<T>& a) {
    auto p = a.m_tail;
    a.m_tail = m_tail;
    m_tail = p;
  }

  void push_front(const T& e) {
    // TODO
  }

  void push_back(const T& e) {
    auto p = new Node(e);
    if(m_tail) {
      p->next = m_tail->next;
      m_tail->next = p;
    } else {
      p->next = p;
    }
    m_tail = p;
  }

  /**
   * 任意位置插入都保证O(1)的复杂性。
   * 但表示位置需要迭代器。
  */
  void insert(const T& e) {
    // TODO
  }

  void reverse() {
    if(!m_tail) {
      return;
    }
    auto pp = m_tail;
    auto pt = m_tail->next;
    for(;pt != m_tail;) {
      auto pn = pt->next;
      pt->next = pp;
      pp = pt;
      pt = pn;
    }
    auto ph = m_tail->next;
    m_tail->next = pp;
    m_tail = ph;
  }

  void print(ostream& ost) const {
    ost << '(';
    if(m_tail) {
      auto p = m_tail->next;
      ost << p->data;
      for(;p = p->next, p != m_tail->next;) {
        ost << ' ' << p->data;
      }
    }
    ost << ')';
  }
};

template<typename T>
ostream& operator<<(ostream& ost, const List<T>& lst) {
  lst.print(ost);
  return ost;
}

int main() {
  List<int> a;
  static_assert(sizeof(a) == sizeof(nullptr));
  cout << a << endl; a.reverse(); cout << a << endl;
  for(int i = 1; i < 9; ++i) {
    a.push_back(i); cout << a << endl; a.reverse(); cout << a << endl;
  }
}